package com.kaizen.leet347;

import java.util.*;

/**
 * 347. 前 K 个高频元素
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 * @author kaizen
 * @date 2020/4/28 22:32
 */
public class SolutionKaizen {


    public int[] topKFrequent(int[] nums, int k) {
        // 堆里面存索引
        Map<Integer, Integer> counterMap = new HashMap<>(nums.length);
        for (int num : nums){
            // 没并发可以用             map.put(num, map.getOrDefault(num, 0) + 1);
            counterMap.compute(num, (key, v) -> {
                if (v == null) {
                    v = 1;
                } else {
                    v += 1;
                }
                return v;
            });
        }
        Heap heap = new Heap(nums.length);
        // // 遍历map，用最小堆保存频率最大的k个元素
        for (Map.Entry<Integer, Integer> entry : counterMap.entrySet()) {
            heap.insert(new Element(entry.getValue(), entry.getKey()));
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = heap.delete().index;
        }
        return res;
    }

    public List<Integer> topKFrequent1(int[] nums, int k) {
        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        // 遍历map，用最小堆保存频率最大的k个元素
        // 优先队列保存k个元素
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        // 取出最小堆中的元素
        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(pq.remove());
        }
        return res;
    }


    public class Element{
        // 频率
        private int frequent;
        // 元素大小
        private int index;

        public Element(int frequent, int index) {
            this.frequent = frequent;
            this.index = index;
        }

        public int getFrequent() {
            return frequent;
        }

        public void setFrequent(int frequent) {
            this.frequent = frequent;
        }

        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }
    }

    /**
     * // 构造最小堆
     * // k是Pop的次数
     */
    public class Heap {
        // 容量
        private int capbility;
        // 元素大小
        private int count;
        // 元素数组
        private Element[] data;

        Heap(int capbility) {
            this.data = new Element[capbility + 1];
            this.capbility = capbility;
            this.count = 0;
        }

        public void insert(Element item) {
            assert (count + 1 <= capbility);
            count++;
            data[count] = item;
            shiftUp(count);
        }

        private void shiftUp(int k) {
            while (k > 1 && data[k].frequent > data[k / 2].frequent) {
                // 与父结点交换
                swap(data, k, k / 2);
                // 继续比较
                k = k / 2;
            }
        }

        public Element delete() {
            assert (count > 0);
            Element item = data[1];
            data[1] = data[count];
            count--;
            shiftDown(1);
            return item;
        }

        private void shiftDown(int k) {
            // 如果有左节点
            while (2 * k <= count) {
                int j = 2 * k;
                // data[j] 是 data[2*k]和data[2*k+1]中的最大值
                if (j + 1 <= count && data[j].frequent < data[j + 1].frequent) {
                    j = j + 1;
                }
                // 与子节点最大的进行比较 如果大于子节点 就直接跳出
                if (data[k].frequent >= data[j].frequent) break;
                // 交换位置和索引继续比较
                swap(data, k, j);
                k = j;
            }
        }


        public void heapify(int[] arr, int n) {
            for (int i = 0; i < n; i++)
                data[i + 1].frequent = arr[i];
            count = n;
            for (int i = n / 2; i >= 1; i--) {
                shiftDown(i);
            }
        }

        public void swap(Element[] arr,int a,int b){
            if(a == b) {
                return;
            }
            Element temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

}
